package com.zk.algorithm;

/**
 * 旋转数组的最小数字，最开始的若干个元素搬到数组的末尾
 *
 * {1,2,3,4,5} => {3,4,5,1,2}
 *
 * 来自剑指 offer
 */
public class FindMinimumInRotatedSortedArray {

    /**
     * 找到最小的数字 - 无重复元素版本
     *
     * 数组中包含两个升序数组: 前半部分 {3,4,5}，后半部分 {1,2}，且前半部分数组的每一个元素都比后半部分数组的元素大。
     * 找到中间元素 array[mid] 如果位于前半部分 (array[mid] >= array[left])，那么最小值在后半部分，left = mid
     * 找到中间元素 array[mid] 如果位于后半部分 (array[mid] <= array[right])，那么最小值在前半部分，right = mid
     *
     * @param array
     * @return
     */
    public int findMin(int[] array) {
        if (array == null || array.length == 0) {
            throw new NullPointerException("array can not be empty");
        }

        return array[findMinIndex(array)];
    }

    /**
     * 找到最小值所在的索引
     *
     * @param array
     * @return
     */
    public int findMinIndex(int[] array) {
        int left = 0;
        int right = array.length - 1;
        int mid = left; // 如果数组整体是排序的，那么默认返回第一个元素

        while (array[left] >= array[right]) { // left 指针总是指向前半部分，right 指针总是指向后半部分

            // =============================
            // 测试案例：[1]
            //              BUG
            //               ↓ == 改为了 <=
            // =============================
            if (right - left <= 1) { // 相差为1 ，证明找到了
                mid = right; // 最小元素永远位于后半部分
                break;
            }

            mid = left + (right - left) / 2;
            if (array[mid] >= array[left]) { // array[mid] 位于前半部分
                left = mid;
            } else if (array[mid] <= array[right]) { // array[mid] 位于后半部分
                right = mid;
            }
        }

        return mid;
    }

    /**
     * 找到最小的数字 - 有重复元素版本
     *
     * 数组中包含两个升序数组: 前半部分 {3,4,5}，后半部分 {1,2}，且前半部分数组的每一个元素都比后半部分数组的元素大。
     * 找到中间元素 array[mid] 如果位于前半部分 (array[mid] >= array[left])，那么最小值在后半部分，left = mid
     * 找到中间元素 array[mid] 如果位于后半部分 (array[mid] <= array[right])，那么最小值在前半部分，right = mid
     *
     * {0,1,1,1,1} => {1, | 0,[1],1,1} => array[mid] = array[left] = array[right] = 1 无法确定 array[mid] 位于哪一个前半部分还是后半部分
     * {0,1,1,1,1} => {1,1,[1], | 0,1} => array[mid] = array[left] = array[right] = 1 无法确定 array[mid] 位于哪一个前半部分还是后半部分
     *
     * 这种情况下只能顺序查找
     *
     * @param array
     * @return
     */
    public int findMin2(int[] array) {
        if (array == null || array.length == 0) {
            throw new NullPointerException("array can not be empty");
        }

        int left = 0;
        int right = array.length - 1;
        int mid = left; // 如果数组整体是排序的，那么默认返回第一个元素

        while (array[left] >= array[right]) { // left 指针总是指向前半部分，right 指针总是指向后半部分

            if (right - left == 1) { // 相差为1 ，证明找到了
                mid = right; // 最小元素永远位于后半部分
                break;
            }

            mid = left + (right - left) / 2;

            // 三个值相同
            // 只能采用顺序查找
            if (array[left] == array[right] && array[mid] == array[left]) {
                return minInOrer(array, left, right);
            }

            if (array[mid] >= array[left]) { // array[mid] 位于前半部分
                left = mid;
            } else if (array[mid] <= array[right]) { // array[mid] 位于后半部分
                right = mid;
            }
        }

        return array[mid];
    }

    // 顺序查找最小值
    private int minInOrer(int[] array, int left, int right) {
        int result = array[left];

        for (int i = left+1; i <= right; ++i) {
            if (array[i] < result) {
                result = array[i];
            }
        }

        return result;
    }

    public static void main(String...args) {
        System.out.println(new FindMinimumInRotatedSortedArray().findMin(new int[]{ 3,4,5,1,2 }));
        System.out.println(new FindMinimumInRotatedSortedArray().findMin2(new int[]{ 1,0,1,1,1 }));
        System.out.println(new FindMinimumInRotatedSortedArray().findMin2(new int[]{ 1,1,1,0,1 }));
    }

}
